package wh.删除链表倒数第n个节点;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/12 15:33
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        System.out.println(removeNthFromEnd(head, 1).val);
    }

    //先计算长度，在删除节点
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode p = head;
        while (p != null){
            length++;
            p = p.next;
        }
        int removeIndex = length - n ;
        if (removeIndex == 0){
            return head.next;
        }
        ListNode q = head;
        int index = 0;
        while (q != null){
            index++;
            if (index == removeIndex){
                q.next = q.next.next;
            }
            q = q.next;
        }
        return head;
    }

    //利用出栈入栈
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    //双指针法 first 和 second\textit{second}second 之间间隔了 n−1n-1n−1 个节点，
    //  即 first\textit{first}first 比 second\textit{second}second 超前了 nnn 个节点
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }



}
